package com.zp.self.module.level_4_算法练习.数据结构.数组;

/**
 * @author By ZengPeng
 */
public class 力扣_73_矩阵置零 {
    //测试
    public static void main(String[] args) {
        int[][] ints;
        ints =new int[][] {{1, 1, 1}, {1, 0, 1}, {1, 1, 1}};
        new 力扣_73_矩阵置零().setZeroes(ints);
        for (int[] anInt : ints) {
            for (int i : anInt)
                System.out.print(i+",");
            System.out.println();
        }

    }

    /**
    题目：给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

     示例 1：
     输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
     输出：[[1,0,1],[0,0,0],[1,0,1]]

     示例 2：
     输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
     输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

    分析：【Good】
       1.使用两个集合存储 需要置为0 的行、列 。再次遍历时将行、列都设置为0
       大神解法：将最外一层:第一行r1、第一列c1用来记录是否为0.
                 A.需要提前记录r1、c1 中是否有0，用于最后将r1,c1置为0的标记
                 B.从[1,1]开始遍历，同步到r1、c1中，哪些行、列 要置为0
                 C.修改每一列的值

    边界值 & 注意点：
       1.
     **/
    public void setZeroes(int[][] matrix) {
        //A.需要提前记录r1、c1 中是否有0，用于最后将r1,c1置为0的标记
        boolean r0 =false,c0=false;
        for (int i = 0; i < matrix[0].length; i++) {//第一行
           if(matrix[0][i] ==0) {
               r0 =true;break;
           }
        }
        for (int i = 0; i < matrix.length; i++) {//第一列
            if(matrix[i][0] ==0) {
                c0 =true;break;
            }
        }
        //B.从[1,1]开始遍历，同步到r1、c1中，置为0
        for (int i = 1; i < matrix.length; i++) {//行
            for (int j = 1; j < matrix[0].length; j++) {//列
                if(matrix[i][j]==0)
                    matrix[i][0]=matrix[0][j]=0;
            }
        }
        //C.修改每一列的值
        for (int i = 1; i < matrix.length; i++) {//行
            for (int j = 1; j < matrix[0].length; j++) {//列
                if(matrix[i][0]==0 || matrix[0][j]==0)
                    matrix[i][j]=0;
            }
        }
        if(r0){
            for (int i = 0; i < matrix[0].length; i++) //第一行 全部改为0
                matrix[0][i]=0;
        }
        if(c0){
            for (int i = 0; i < matrix.length; i++)//第一列 全部改为0
                matrix[i][0] =0;
        }
    }
}
